Chip 1996 April/CHIP 1996 aprilis (CD06).zip/CHIP_CD06.ISO/hypertxt.arj/92/ERT9207.CD

Text File | 1995-09-15 | 15KB | 435 lines

      @VSzámok párban, pontosan, avagy júliusi rejtvényeink
      megfejtéseirôl@N

      @VKezdjük barátságosan...@N

          A  feladat  egy  olyan   program  írása  volt,  mely   a
      barátságos   számpárokat  állítja   elô  megadott   határig.
      Emlékeztetô gyanánt: barátságos számoknak nevezzük azokat  a
      számpárokat,  ahol  az  egyik  szám  nála  kisebb  osztóinak
      összege egyenlô a másik számmal és viszont. Ilyen  számpárok
      tízezerig:
          220 és 284
          1184 és 1210
          2620 és 2924
          5020 és 5564
          6232 és 6368
          Látható, hogy ezek a számpárok elég ritkán találhatók  a
      számegyenesen,  tehát  a   sikerélményhez  --  jó   sok  pár
      megtalálásához -- elég nagy számokat kell megvizsgálnunk. Ez
      viszont  drámai  hatással  lehet  a  program   futásidejére,
      legalábbis  ha  nem  járunk  el  gondosan.  A  megfejtésként
      érkezett nyolc  program között  volt olyan  -- jellegzetesen
      ""adj,  Uram,  de rögtön"  stílusban  készült, amúgy  mûködô
      eljárás -- amely a  fentebb leírt számok megtalálására  több
      mint  három  órát  fordított,  pontosabban  rabolt.  (Ebéd +
      csendespihenô +  ...) Ez  bizony sok,  különösen ha  tudjuk,
      hogy ezeket a számokat 10-20 másodperc alatt is megkaphatjuk
      (például  Tamás  István  megoldása  szerint,  bár  az általa
      választott  út  némileg  egyedi,  lásd  késôbb).  Talán  nem
      tanulság nélküli  végignézni, hogy  mi módon  jutunk el  egy
      elsô, alacsony hatékonysággal mûködô programkezdeménytôl  --
      apró,  végeredményben  kézenfekvô  ötletekkel  --  egy közel
      optimális, gyors ""végsô" változatig.
          Az alapötlet algoritmusát  így írhatnánk le  (megoldóink
      többsége is így indult el):
          @Kbarátságos számok;
          osztoösszeg(szam);
        ciklus i=1-tôl szam/2-ig
            ha i osztja szam-ot akkor summa=summa+i
        ciklus vége
          eljárás vége
          ciklus szam=1-tôl hatar-ig
        temp=osztoösszeg(szam)
        ha osztoösszeg(temp)=szam akkor kiir(szam,temp)
          ciklus vége
          program vége.@N
          Ennyi az egész... meg a több órás futásidô. Mit  lehetne
      itt tenni, hogy kicsit ügyesebben mûködjön mûvünk?
          Elsô  menetben   az  osztók   összegének  meghatározását
      javítjuk, felismerve azt az elemi tényt, hogy ha a 3 osztója
      a 12-nek,  akkor a  12/3 is  az. Ezzel  az ötlettel elérjük,
      hogy már  nem a  számok feléig,  hanem csak  a gyökükig kell
      ""elgyalogolni".   Tessék    utánaszámolni,   hány    lépést
      takarítunk meg ezzel, mondjuk 100000-ig vizsgálódva! Persze,
      valamit  valamiért:  jelentkezik   egy  pici  csapda,   amit
      valahogyan ki kell majd kerülnünk. Tudniillik, egy osztót és
      a párját (például 3 és 12/3) egyszerre kell összegeznünk, de
      például a  36 esetében  ezt nem  szabad megtennünk  a 6-tal!
      Azaz  lett  egy  plusz  feltételvizsgálatunk,  de  mi  ez  a
      lépésszám csökkenéséhez képest!
          Második apró  ötletünk: ha  az osztók  összege kisebb  a
      ciklusban  éppen  soros  számnál,  már  ejtjük  is,   hiszen
      korábban már megvizsgáltuk  (mellesleg így egy  számpár csak
      egyszer  íródik ki).  Konkrétan: a  220-hoz megvizsgáljuk  a
      284-t (s  mivel jó,  kiírjuk), de  már a  284-nél tartva, az
      összegként jelentkezô 220-nak nem szedjük össze az  osztóit.
      Azaz   újra   egy   további   feltétel,   de   nyerünk    az
      osztószámláláson.
          A harmadik  ötlet a  második továbbgondolásával  adódik:
      jelöljük  meg  mindig a  ""letudott"  számokat (például  egy
      logikai változóval, tömbbel) és ha véletlenül egy ilyen, már
      elemzett szám kerülne elénk, akkor ugorjuk át.
          A  három  kis módosítás  pillanatok  alatt beírható,  az
      eredmény  pedig  meggyôzô: programunk  több  mint ötszázszor
      gyorsabb  lett!  (A  tízezres  határig  menô  vizsgálat   25
      másodpercet vesz igénybe egy  mezei AT-n a mellékelt  listán
      látható programmal, mely Gyombolai Márton és Horváth  Sándor
      munkájának ""összegyúrásával" készült.)
          Némileg  másként  járt   el  Tamás  István.   Az  alábbi
      számelméleti tétel  felhasználásával oldotta  meg az  osztók
      összegének  elôállítását.  Tudván, hogy  ha  egy egész  szám
      prímtényezôs felbontása
          @Kp^a*q^b*...z^h@N
          ahol @Kp,q,...z@N különbözô prímszámok, @Ka,b,...h@N a  kitevôk,
      akkor az @Kn@N osztóinak összege:
          sigma   =   (1+p+p^2+...+p^a)*(1+q+q^2+...+q^b)*    ...*
      (1+z+z^2+...+z^h)
          mely  összegbôl  ezúttal   természetesen  @Kn@N-t  le   kell
      vonnunk. A függvényt felhasználva programunk még  körülbelül
      kétszeresére, háromszorosára gyorsítható.
          A  helyes megoldást  beküldôk közül  a sorsolás  Horváth
      Sándornak  kedvezett,  a  doboznyi  Tungsram  floppyt postán
      küldjük el.


      @VPI-t csak pontosan, szépen...@N

          Mindenesetere pontosabban és szebben, mint ahogy júliusi
      számunkban a rejtvény szövege megjelent. Természetesen nincs
      arról szó, hogy valami titkos egyezmény született volna  eme
      érdekes szám új  jelölésérôl, hogy a  jól bevált görög  betû
      helyett ezentúl a ""*" lenne használatos, mint ahogy az  sem
      igaz, hogy a négyzetgyök 2 az
          x^2=0 egyenlet megoldása az
          x^2-2=0 egyenlet helyett.
          ùjfent: mea maxima  culpa... Szerencsére megoldóinkat  e
      bosszantó apróságok nem zavarták meg. Kilenc helyes megoldás
      érkezett.  Több  megfejtônk  --  Dudás  János,  Fodor Zsolt,
      Gyombolai Márton -- tanulmány értékû dokumentációt mellékelt
      programjához. A  megfejtéseket egy  kivételével mind  Pascal
      nyelven írták. (Érdemes lenne egyszer komolyan  megvizsgálni
      a   kérdést,  hogy   mi  lehet   az  oka   e  nyelv   ekkora
      népszerûségének. Ennyire ""kitalálta" Wirth, vagy ilyen  jól
      dolgoztak  a Borland  fejlesztôi --  mindenki Turbo  Pascalt
      használt --, vagy valami egészen más oka van a dolognak?)
          A   feladat  tehát   a  PI   elsô  100   tizedesjegyének
      meghatározása volt. A megoldás két alapvetô részbôl  rakható
      össze:    egyrészt    kell   egy    közelítô    eljárás   PI
      meghatározására, másrészt  -- mivel  a programozási  nyelvek
      implementációi   körülbelül    20   tizedesjegy    maximális
      pontosságot tesznek  lehetôvé --  szükségünk van  a 100 jegy
      pontosságot megvalósító  adatreprezentációra, illetve  ilyen
      nagypontosságú matematikai mûveletekre. A program  megírása,
      felépítése  során  több  döntési  lehetôségünk  van,  de   e
      döntések  nem  függetlenek  egymástól.  Például  a  közelítô
      eljárás megválasztásakor szempont  lehet a gyorsasága,  de a
      programozhatósága  is:   tudniillik  mely   mûveletekre  (és
      hányra) kell megírni a százjegyû aritmetikát. Lássuk elôször
      a közelítés kérdését!
          A megoldások tanúsága  szerint két irányban  indulhatunk
      el: geometriai  vagy analízisbéli  eszközöket használva.  Az
      elôbbi   módszert    egyedül   Dudás    János   választotta.
      Gondolatmenete azért  érdekes, mert  bizonyítja, hogy  elemi
      eszközöket használva is megoldható a feladat. Olvasónk egy 2
      egység  sugarú  körbe  írt  szabályos  négyszög,  nyolcszög,
      tizenhatszög,   stb.   sorozat   kerületét   számolta    ki.
      Nyilvánvaló, hogy így PI  négyszereséhez -- elég gyorsan  --
      közelítô  értéket  kapunk,  mindössze  a  Pithagorasz-tételt
      használva. De ebbôl származik egy gond is: a sorozat képlete
      négyzetgyökvonást  tartalmaz,  tehát meg  kellett  írnia egy
      gyökvonó  algoritmust is,  hiszen a  beépített függvény  nem
      dolgozik a kívánt pontossággal. Többi megfejtônk a  végtelen
      sorok elméletéhez fordult a megfelelô közelítést  keresendô.
      Volt  aki  az  úgynevezett  Leibnitz  sor  mellett  döntött,
      melynek alakja:
          PI/4 = 1 - 1/3 + 1/5 - 1/7 + ...
          Az   egyszerû    képlettel   megadható    (az   arctg(x)
      hatványsorából származó) sorral szemben egy -- ámde döntô --
      érv  hozható  fel:  rendkívül  lassan  konvergál.  Hiszen  a
      közelítés pontosságát jól jellemzi az utolsó számított  tag,
      melynek nagysága
          @K1/(2*n+1)@N
          Ennek kell
          @K10^-100@N <****10 a minusz századikon****>
          -nál  kisebbnek  lennie,  ami  körülbelül  10^100 lépést
      igényel!  A  program  futásidejének  megbecsülésére  nem  is
      vállalkozom.   Gyorsabbnak  tûnik   az  arcsin(x)   függvény
      hatványsorából képzett közelítés:
              1  1      3     1     3∙5    1
          p = 3∙[1 + ─── ─ + ─────── ── + ─────── ─── +...]
             2∙3 8   22∙2!∙5 32   23∙3!∙7 128
          vagy  a  Machin-féle sor  (melyet  arctg(x) segítségével
      kaphatunk meg):
            ┌                            ┐
         pi     │ 1   1 ┌ 1 ┐3  1 ┌ 1 ┐5  1 ┌ 1 ┐7      │
         -- = 4 │ - - - │ - │ + - │ - │ - - │ - │ + ... │
          4     │ 5   3 └ 5 ┘   5 └ 5 ┘   7 └ 5 ┘       │
            └                            ┘
          ┌                              ┐
          │  1    1 ┌  1  ┐3  1 ┌  1  ┐5  1 ┌  1  ┐7      │
        - │ --- - - │ --- │ + - │ --- │ - - │ --- │ + ... │
          │ 239   3 └ 239 ┘   5 └ 239 ┘   7 └ 239 ┘       │
          └                              ┘
          esetleg a Wallis-formula:
          @Kpi/2 = 2/1*2/3*4/3*4/5*6/5*6/7*...@N
          (Ezek,  s  más,   PI-t  eredményezô  sorok,   lánctörtek
      megtalálhatók például @KCourant-Robbins: Mi a matematika@N  címû
      könyvében). A megfejtések  -- melyek ezeket  a közelítéseket
      alkalmazták -- azt bizonyítják,  hogy ez a három  utóbbi sor
      jól  használható  (elég  gyorsak:  egy  286-oson  futtatva a
      programokat 10-40 másodperc közötti idôk adódtak),  feltéve,
      hogy a kiegészítô eljárások elég hatékonyak. (Volt megfejtô,
      akinek  sikerült  a  Machin-sort  alkalmazva  ""15   perces"
      programot írnia). Döntenünk kell a pontosság  ellenôrzésének
      kérdésében:  folyamatosan,  ciklusonként  megnézzük-e  (mint
      Déri  Attila),  vagy  elôzetesen  megbecsüljük  a  szükséges
      lépésszámot,  s  az  alkalmazandó  jegyek  számát (Gyombolai
      Márton  járt  el  így)  --  ez  gyors,  viszont  matematikai
      jártasságot követel.
          Nem elhanyagolható kérdés a számjegyek nyilvántartásának
      ügye: választhatjuk a szöveges ábrázolást (mint tette  Fodor
      Zsolt), vagy a tömbös megvalósítást (Tóth László és  mások).
      A  másik  probléma  természetesen  a  mûveletek:  volt   aki
      szimulálta  a  ""kézi"  eljárásokat,  volt  aki  teljesen új
      algoritmusokat konstruált, mondjuk 10000-es számrendszerben.
      Mindezek   eredményeképpen   a   programoknak   egy   színes
      választéka  jött létre,  s kár,  hogy nem  tudjuk  mindegyik
      változatot  közölni.  A   mellékelt  lista  Horváth   Sándor
      programját mutatja.
          Ålljon itt végezetül PI  elsô 100 tizedesjegye, mely  --
      Verbôczi  Zoltán szíves  közlése nyomán  -- ellenôrizhetô  a
      Középiskolai Matematikai Lapok  1983. évi 1.  számának hátsó
      borítóján megtalálható 950 jegyû táblázat alapján.
          14159 26535  89793 23846  26433 83279  50288 41971 69399
      37510 58209 74944 59230 78164 06286 20899 86280 34825  34211
      70679

      @KBánhegyesi Zoltán@N

program barat;

var  i,n,nbarat,ioszt : word;
var  kesz: array[1..10000] of boolean;


function OsztokOsszege(szam:word): word;

var i,sum,fhat: word;

begin
   sum := 1;          { Az 1 biztosan osztó }
   fhat := trunc(sqrt(szam))+1;
   for i := 2 to fhat do
     if (szam mod i) = 0 then begin
          inc(sum,i);
          if i<>szam div i then inc(sum,szam div i);
          end;
   OsztokOsszege := sum;
end;



BEGIN
   write('A felsô határ (maximum 10000):');
   read(n);
   for i := 1 to n do kesz[i] := false;
   nbarat := 0;

   for i := 2 to n do
   if not kesz[i]
   then begin
     if OsztokOsszege(i) > i
     then begin
       ioszt := OsztokOsszege(i);
       if OsztokOsszege(ioszt) = i
       then begin
     nbarat := nbarat+1;
     writeln(nbarat:4,'. barátságos számpár: ',i:5,' és ',ioszt:5);
     kesz[ioszt] := true;
       end;
     end;
     kesz[i] := true;
   end;
END.
---------

program Pijegyek;
{ Horváth Sándor, Barcs}

uses crt;

const
  Jegy  = 100;
  Hossz = (jegy div 4) + 3 ;

type
  Longreal  = array[1..Hossz] of word;
  LongReal2 = array[1..2*Hossz] of longint;

var
  Long0  : LongReal;
  Long00 : LongReal2;

procedure osszead(a,b : Longreal ; var c : Longreal);
var
  m,i : word;
  z : longint;
begin
  c:=Long0;
  m:=0;
  for i:=Hossz downto 1 do begin
    z:=longint(a[i])+b[i]+m;
    m:=z div 10000;
    c[i]:=z mod 10000;
  end;
  if m>0 then begin
    writeln('Túlcsordulás az összeadásnál!');
    halt(1);
  end;
end;

procedure kivon(a,b : Longreal ; var c : Longreal);
var
  m,i : word;
begin
  m:=0;
  for i:=Hossz downto 1 do begin
    if a[i]>=b[i]+m
    then begin
      c[i]:=a[i]-b[i]-m;
      m:=0;
    end else begin
      c[i]:=10000+a[i]-b[i]-m;
      m:=1;
    end;
  end;
  if m>0 then begin
    writeln('Túlcsordulás a kivonásnál!');
    halt(1);
  end;
end;

procedure szoroz(a,b : Longreal; var c : Longreal);
var
  i,j,k : word;
  z,mm : longint;
  e : longreal2;
begin
  e:=Long00;
  for j:=Hossz downto 1 do begin
    for i:=Hossz downto 1 do begin
      z:=longint(a[i])*b[j];
      k:=i+j-1;
      inc(e[k],z);
      mm:=e[k] div 10000;
      while (mm>0) and (k>0) do begin
    e[k]:=e[k] mod 10000;
    dec(k);
    inc(e[k],mm);
    mm:=e[k] div 10000;
      end;
      if k=0 then begin
    writeln('Túlcsordulás a szorzásnál !');
    halt(1);
      end;
    end;
  end;
  for i:=1 to Hossz do c[i]:=e[i];
end;

procedure ByteSzoroz(a : LongReal; b : byte; var c : LongReal);
var
  i : word;
  x,m : longint;
begin
  c:=Long0;
  m:=0;
  for i:=Hossz downto 1  do begin
    x:=longint(a[i])*b+m;
    c[i]:=x mod 10000;
    m:=x div 10000;
  end;
  if m>0 then begin
    writeln('Túlcsordulás a byte szorzásnál !');
    halt(1);
  end;
end;

procedure EgyetOszt(a:longint; var c : Longreal);
var
  sz,m : longint;
  i : word;
begin
  m:=0;
  sz:=1;
  c:=Long0;
  for i:=1 to Hossz do begin
    c[i]:=sz div a;
    m:=sz mod a;
    sz:=m*10000;
  end;
end;

procedure Kiir(a : LongReal);
var
  i : word;
begin
  write(a[1],'.');
  for i:=2 to Hossz do
  case a[i] of
    0..9 : write('000',a[i]);
    10..99 : write('00',a[i]);
    100..999 : write('0',a[i]);
    else write(a[i]);
  end;
  writeln;
end;

function Egyenlo(a,b : LongReal) : boolean;
var i : word;
begin
  i:=1;
  while (i<=Hossz) and (a[i]=b[i]) do inc(i);
  Egyenlo:=i>Hossz;
end;

var
  pi_Szam, Pi_regi, a1_5, a1_239, a, b, c, c1, c2 : LongReal;
  sig,i : word;

begin
  ClrScr;
  for i:=1 to hossz do Long0[i]:=0;
  for i:=1 to 2*hossz do Long00[i]:=0;
  pi_Szam:=Long0;
  EgyetOszt(5,a1_5);
  EgyetOszt(239,a1_239);
  a:=a1_5;
  b:=a1_239;
  szoroz(a1_5,a1_5,a1_5);
  szoroz(a1_239,a1_239,a1_239);
  sig:=1;
  i:=1;
  ClrScr;
  repeat
    Pi_regi:=Pi_szam;
    ByteSzoroz(a,16,c1);
    ByteSzoroz(b,4,c2);
    Kivon(c1,c2,c);
    EgyetOszt(i*2-1,c1);
    Szoroz(c,c1,c);
    if sig=1 then Osszead(pi_Szam,c,pi_Szam) else Kivon(pi_Szam,c,pi_Szam);
    sig:=1-sig;
    GotoXY(1,1);
    writeln(i,'. iteráció');
    szoroz(a,a1_5,a);
    szoroz(b,a1_239,b);
    inc(i);
  until egyenlo(pi_szam,pi_regi);
  writeln;
  write('pi = ');
  kiir(pi_szam);
  repeat until keypressed;
end.